#pragma once
#include <iostream>
#include <vector>
namespace MySort
{
    void Swap(int &a, int &b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    // 打印
    void Print(const std::vector<int> &arr)
    {
        for (auto &e : arr)
        {
            std::cout << e << " ";
        }
        std::cout << std::endl;
    }
    // 插入排序
    // 直接插入排序
    void InsertSort(std::vector<int> &arr)
    {
        // i 代表 有序序列的末尾元素下标
        for (int i = 0; i < arr.size(); ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (arr[j] > arr[i])
                {
                    int tmp = arr[i];
                    int tmp_pos = i;
                    while (tmp_pos > j)
                    {
                        arr[tmp_pos] = arr[tmp_pos - 1];
                        --tmp_pos;
                    }
                    arr[tmp_pos] = tmp;
                }
            }
        }
    }
    // 希尔排序
    void ShareSort(std::vector<int> &arr)
    {
        // 4 9 2 3 1 5 8 4
        // 分组
        int gap = arr.size() / 2;
        // 组别
        for (; gap > 1; gap = gap / 3 + 1)
        {
            // 每组的起始位置
           for(int i = 0; i < gap; ++i)
           {

           }
        }
        InsertSort(arr);
    }
    // 选择排序
    // 直接选择排序
    void ChooseSort(std::vector<int> &arr)
    {
        // 5 2 5 1
        for (int i = 0; i < arr.size(); ++i)
        {
            int min_sum = arr[i]; // 最小元素
            int pos = i;          // 最小元素位置

            for (int j = i; j < arr.size(); ++j)
            {
                // 找出未排序区间最大/最小元素
                if (min_sum > arr[j])
                {
                    min_sum = arr[j];
                    pos = j;
                }
            }
            // 交换
            Swap(arr[i], arr[pos]);
        }
    }
    // 堆排序
    void HeapSort()
    {
    }
    // 交换排序
    // 冒泡排序
    void BullueSort(std::vector<int> &arr)
    {
        for (int i = arr.size() - 1; i >= 0; --i)
        {
            for (int prev = 0, next = 1; next <= i; ++prev, ++next)
            {
                if (arr[prev] > arr[next])
                {
                    Swap(arr[prev], arr[next]);
                }
            }
        }
    }
}
